package edu.siu.math.egut.util;

import java.io.Serializable;
import java.util.Arrays;

/**
 * A data structure for storing the Cayley table for addition of vectors.
 * 
 * More explicitly, this is initialized at the start so that any time two
 * roots are added, the result is obtained from this table. This is faster
 * than simply adding two roots and checking the result.
 * 
 * @author Joe Pleso
 * 
 */
public class VectorCayleyTable implements Serializable {

    /**
     * 
     */
    private static final long serialVersionUID = 126L;
    private final int[][] matrix;
    /**
     * the number of rows/columns in the Cayley table
     */
    public final int length;
    private final int[][] roots;

    /**
     * Create a new Cayley table for vectors over addition.
     * @param  r  a finite list of vectors  (tuples of integers) 
     * 
     * 
     * 
     */
    public VectorCayleyTable(int[][] r) {/*@\label{vctconst}@*/
        roots = r;
        length = roots.length;
        int n = length;
        matrix = new int[((n * (n - 1)) / 2)][roots[0].length];
        int[] temp = new int[roots[0].length];
        for (int i = 0; i < roots.length - 1; i++) {
    	    for (int j = i + 1; j < roots.length; j++) {
    	        for (int k = 0; k < temp.length; k++)
    		    temp[k] = (roots[i][k] + roots[j][k]);
    	        int k = findIndex(temp);
    	        int[] image;
    	        if (k < 0)
    		    image = null;
    	        else
    		    image = roots[k];
    	        set(i, j, image);
    	    }
        }
    }/*@\label{vctconstend}@*/

    /**
     * Adds two vectors, using a Cayley table.  Result will be the sum 
     * of the two vectors, if it was a member of the list used to 
     * initialize the table, and null if not.
     * 
     * @param iRoot the first vector
     * @param jRoot the second vector
     * @return the sum or null if the sum is not on the list provided
     * 
     */
    public int[] add(int[] iRoot, int[] jRoot) {/*@\label{vctadd}@*/
        int i = findIndex(iRoot);
        int j = findIndex(jRoot);
        if( i>-1&&j>-1) {
            if (j < i)
    	        return (add(jRoot, iRoot));
            if( i == j )
                return null;
            
            i++;
            j++;
            int n = length;
            return matrix[((((2 * n) - i) * (i - 1)) / 2) - i + j - 1];
        }
        throw new RuntimeException();
	
	//int[] c = new int[8];
	//for (int i = 0; i < 8; i++)
	//    c[i] = iRoot[i] + jRoot[i];
	//int index = findIndex(c);
	//if (index == -1)
	//    return null;
	//return roots[index];
    }/*@\label{vctaddend}@*/

    /**
     * Return the list of roots that was used to initialize this table.
     * 
     * @return the list of roots
     */
     public int[][] getRoots() {/*@\label{vctgetRoots}@*/
        return roots;
    }/*@\label{vctgetRootsend}@*/

    private void set(int i, int j, int[] x) {
        if (j < i)
    	    set(j, i, x);
        else {
    	    i++;
    	    j++;
    	    int n = length;
    	    matrix[((((2 * n) - i) * (i - 1)) / 2) - i + j - 1] = x;
        }
    }

    /**
     * Subtracts two vectors from the list of vectors that was used to
     * construct this table.
     * 
     * @param a            the first vector
     * @param b            the second vector
     * @return returns the vector a-b if it was in the original list (and
     *         null if not).
     */
    public int[] subtract(int[] a, int[] b) {/*@\label{vctsubtract}@*/
        int bIndex = findIndex(b);
        for (int i = 0; i < bIndex; i++)
    	    if (Arrays.equals(add(roots[i], b), a))
    	        return roots[i];
        for (int i = bIndex + 1; i < roots.length; i++)
    	    if (Arrays.equals(add(b, roots[i]), a))
    	        return roots[i];
        return null;
    }/*@\label{vctsubtractend}@*/
    

/**
 * Finds the index of root in the int[][] roots
 * 
 * @param roots
 *            a int[][] to search in
 * @param root
 *            a int[] to find in roots
 * @return the index such that roots[index]==root is true, or -1 if a match
 *         was not found
 */

    private int findIndex(int[][] roots, int[] root) {
	for (int i = 0; i < roots.length; i++)
	    if (Arrays.equals(root, roots[i]))
		return i;
	return -1;
    }

    int findIndex(int[] root) {
	return findIndex(roots, root);
    }
    
    /**
     * Test efficiency.
     * 
     * @param args ignored
     */
    public static void main (String[] args) {/*@\label{vctmain}@*/
	ExceptionalGroup g = ExceptionalGroup.getGroup(8);
	VectorCayleyTable vct = new VectorCayleyTable(g.getRoots());
	int[] a = g.getPositiveRoots()[0];
	
	long time = System.currentTimeMillis();
	for (int i = 1; i <= 30000000; i++) {
	    vct.add(a, g.getPositiveRoots()[i % 30]);
	}
	time -= System.currentTimeMillis();
	
	System.out.println(time);
	//current implementation 18.409 sec
	//old implementation 105.327 sec
    }/*@\label{vctmainend}@*/
}
